package com.dataStructure.跳表;

import java.util.Comparator;

@SuppressWarnings("unchecked")
public class SkipList<K, V> {
    /**
     * 限制跳表的最高层级为32
     */
    private final static int MAX_LEVEL = 32;
    /**
     * t
     */
    private final static double P = 0.25;
    private final Comparator<K> comparator;
    private int size;
    /**
     * 有效层数
     */
    private int level;

    /**
     * 不存放任何K-V的首节点(首元节点)
     */
    private Node<K, V> first;

    public SkipList(Comparator<K> comparator) {
        this.comparator = comparator;
        first = new Node<>(null, null, MAX_LEVEL);
        first.nexts = new Node[MAX_LEVEL];
    }

    public SkipList() {
        this(null);
    }

    /**
     * 随机决定一个节点的层数
     *
     * @return
     */
    private int randomLevel() {
        int level = 1;
        while (Math.random() < P && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

    private void keyCheck(K key) {
        if (key == null)
            throw new IllegalArgumentException("key must not be null!");
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 往跳表里面放入元素
     *
     * @param key
     * @param value
     * @return 若key已存在，则存新value，返回旧value
     */
    public V put(K key, V value) {
        keyCheck(key);
        Node<K, V> node = this.first;
        Node<K, V>[] prevs = new Node[level];

        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            //下一个为空或者下一个比key小
            while (node.nexts[i] != null
                    && (cmp = compare(key, node.nexts[i].key)) > 0) {
                node = node.nexts[i];
            }
            //cmp == 0 说明node是存在的 用新值覆盖原值 并返回原值
            if (cmp == 0) {
                V oldValue = node.nexts[i].value;
                node.nexts[i].value = value;
                return oldValue;
            }
            prevs[i] = node;
        }

        //新节点层数
        int newLevel = randomLevel();
        //添加新节点
        Node<K, V> newNode = new Node<>(key, value, newLevel);

        //设置新节点的前驱和后继
        for (int i = 0; i <= newLevel; i++) {
            if (i >= level){
                first.nexts[i] = newNode;
            }else {
            //设置后继
            newNode.nexts[i] = prevs[i].nexts[i];
            //设置前驱
            prevs[i].nexts[i] = newNode;}
        }
        //增加节点数量
        size++;
        //计算跳表的最终层数
        level = Math.max(level, newLevel);
        return null;
    }

    /**
     * 获取节点
     * @param key
     * @return
     */
    public V get(K key) {
        keyCheck(key);
        Node<K, V> node = this.first;
        int cmp = -1;
        for (int i = level - 1; i >= 0; i--) {
            //下一个为空或者下一个比key小
            while (node.nexts[i] != null
                    && (cmp = compare(key, node.nexts[i].key)) > 0) {
                node = node.nexts[i];
            }
            //cmp == 0 说明node.nexts[i].key跟key一样大，即找到了，就返回即可
            if (cmp == 0) return node.nexts[i].value;
        }
        return null;
    }

    /**
     * 删除节点
     * @param key
     * @return
     */
    public V remove(K key) {
        keyCheck(key);

        Node<K, V> node = this.first;
        Node<K, V>[] prevs = new Node[level];
        boolean exist = false;
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            //下一个为空或者下一个比key小
            while (node.nexts[i] != null
                    && (cmp = compare(key, node.nexts[i].key)) > 0) {
                node = node.nexts[i];
            }
            prevs[i] = node;
            //cmp == 0 说明node是存在的 用新值覆盖原值 并返回原值
            if (cmp == 0){
                exist = true;
            }
        }
        //要删除的元素不存在
        if (!exist) return null;
        //需要删除的节点
        Node<K,V> removeNode =  node.nexts[0];
        //数量减少
        size --;
        //设置后继
        for (int i = 0; i <= removeNode.nexts.length ; i++) {
            prevs[i].nexts[i] = removeNode.nexts[i];
        }
        // 更新跳表的层数
        int newLevel = level;
        while (--newLevel >= 0 && first.nexts[newLevel] == null) {
            level = newLevel;
        }
        
        return removeNode.value;
    }

    public int compare(K k1, K k2) {
        return comparator != null
                ? comparator.compare(k1, k2)
                : ((Comparable<K>) k1).compareTo(k2);
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V>[] nexts;

        public Node(K key, V value, int level) {
            this.key = key;
            this.value = value;
            this.nexts = new Node[level];
        }
    }
}
